package 中等.栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
 * () 得 1 分。
 * AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
 * (A) 得 2 * A 分，其中 A 是平衡括号字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/score-of-parentheses
 */
public class 括号的分数_856 {

    public static void main(String[] args) {

        System.out.println(scoreOfParentheses("(()(()))"));

    }

    /**
     * 遍历字符串，遇见 ( 加入栈中
     * 1，遇见 ) ，且栈顶元素是 ( ，取出栈顶 ( ，将 1 放入栈顶，--> () 得 1 分
     * 2，
     * a，遇见 ) ，且栈顶元素是 数字，那么取出所有 栈顶连续数字，累加 --> A + B
     * b，将 栈顶连续数字累加和 * 2 的结果放入栈顶，--> (A)
     * <p>
     * 最后将栈里面的所有数字累加即为答案
     * 技巧：
     * -1 代替 (
     *
     * @param s
     * @return
     */
    public static int scoreOfParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            // -1 代替 (
            if (c == '(') {
                stack.addFirst(-1);
            } else {
                if (stack.peekFirst() == -1) {
                    stack.pollFirst();
                    stack.addFirst(1);
                } else {
                    int sum = 0;
                    while (stack.peekFirst() != -1) {
                        sum += stack.pollFirst();
                    }
                    stack.pollFirst();

                    stack.addFirst(sum * 2);
                }
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pollFirst();
        }
        return ans;
    }

}
